package sort

//插入排序
//时间复杂度O(N^2),空间复杂度O(1)
//https://www.cnblogs.com/ghj1976/archive/2013/02/28/2937029.html
func InsertSort(arr []int) {
	length := len(arr)

	for i := 1; i < length; i++ {
		temp := arr[i] //暂存未排序区间第一个元素
		j := i         //j指针指向未排序第一个

		for j > 0 && arr[j-1] > temp { //temp值更小
			arr[j] = arr[j-1] //元素后移
			j--               //指针迁移，继续比较前一个已排序数
		}

		//判断是否发生后移，如果有说明未排序区存在更小的值
		if j != i {
			arr[j] = temp
		}
	}
}

//希尔排序是对插入排序的一种改进，将增量由1变成了>=1的数
func ShellSort(arr []int) {
	length := len(arr)
	incr := length - 1

	for incr > 0 {
		//插入排序
		for i := incr; i < length; i++ {
			temp := arr[i]
			j := i
			for j > 0 && arr[j-incr] > temp {
				arr[j] = arr[j-incr]
				j = j - incr
			}

			if i != j {
				arr[j] = temp
			}
		}

		incr = incr / 2
	}
}
